import tool.TreeNode;
import tool.TreeNodePrint;
import tool.input;

import java.util.Stack;

/**
 * @Description:
 * @Date:Create in 23:50  2022/7/30
 */
public class hasPathSum0112 {
    public static void main(String[] args) {
        String s = "[1,2,3]";
        int sum = 5;
        TreeNode root = input.getTree(s);
        TreeNodePrint.printTree(root);
//        testIf();
//        bfs(root);
//        testGetFirst();
        System.out.println(Dfs(root,sum));

    }

    //递归方法
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        return Dfs(root,targetSum);
    }

    public static boolean Dfs(TreeNode root, int sum) {
        if(root==null) return false;
        if (root.val == sum && root.left == null && root.right == null) return true;
        sum -= root.val;
        boolean left = Dfs(root.left,sum);
        boolean right = Dfs(root.right,sum);
        return left||right;
    }

    //迭代方法
//    public static boolean hasPathSum2(TreeNode root, int targetSum) {
//        if(root == null ) return false;
//        Stack
//    }
}
